package 题目集.线段树or树状数组.树状数组;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * 树状数组可以维护最值的情况非常受限。
 * 只能支持向上更新，以及前缀最值。
 */
public class ch08_树状求前缀最值 {
    static class TreeArray {
        public TreeArray(int[] src) {
            n = src.length;
            tree = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                updateMax(i, src[i - 1]);
            }
        }

        int[] tree;
        int n;

        public void updateMax(int i, int v) {
            for (; i <= n; i += lowbit(i)) {
                tree[i] = Math.max(tree[i],v);
            }
        }
        public int query(int i) {
            int ans = 0;
            for (; i > 0; i -= lowbit(i)) {
                ans = Math.max(ans, tree[i]);
            }
            return ans;
        }

        public int lowbit(int x) {
            return x & -x;
        }
    }

    static class Ans {
        private int[] src;
        private int n;

        public Ans(int[] src) {
            this.src = src;
        }

        public void updateMax(int i, int v) {
            src[i-1] = Math.max(src[i-1],v);
        }

        public int query(int i) {
            int ans = 0;
            for (int j = 0; j < i; j++) {
                ans = Math.max(ans, src[j]);
            }
            return ans;
        }
    }

    @Test
    public void test2(){
        int[] arr={49, 10, 95, 32, 50};
        TreeArray treeArray = new TreeArray(arr);
        System.out.println(treeArray.query(1));
    }
    @Test
    public void test() {
        int count = 10000;
        int maxn = 5000;
        int maxv = 1000;
        int cnt=100;
        for (int i = 0; i < count; i++) {
            compare(maxn,maxv,cnt);
        }
    }
    static Random r=new Random();
    public static void compare(int maxn,int maxv,int cnt){
        int n=r.nextInt(maxn)+1;
        int[] src=new int[n];
        for (int i = 0; i < n; i++) {
            src[i]=r.nextInt(maxv)+1;
        }
        TreeArray treeArray = new TreeArray(src.clone());
        Ans ans = new Ans(src.clone());
        int[][] op=new int[cnt][3];
        for (int i = 0; i < cnt; i++) {
            op[i][0]=r.nextInt(2)+1;
            op[i][1]=r.nextInt(n)+1;
            if(op[i][0]==1){
                op[i][2]=r.nextInt(maxv)+1;
                treeArray.updateMax(op[i][1],op[i][2]);
                ans.updateMax(op[i][1],op[i][2]);
            }else {
                int fun=treeArray.query(op[i][1]);
                int an=ans.query(op[i][1]);
                if(fun!=an){
                    System.out.println("error");
                    System.out.println(Arrays.toString(src));
                    for (int[] ints : op) {
                        System.out.println(Arrays.toString(ints));
                    }
                    System.out.println("实际："+fun+"；\t预计："+an);
                    treeArray.query(op[i][1]);
                    int a=1/0;
                }
            }
        }
    }
}
